import collections
from typing import List

MAX_INT = 10 ** 10


class Solution:
    def shortestPath(self, grid: List[List[int]], k: int) -> int:
        m, n = len(grid), len(grid[0])

        def _is_valid(x, y):
            return 0 <= x < m and 0 <= y < n

        def neighbors(x1, y1):
            return [(x2, y2) for (x2, y2) in [(x1 - 1, y1), (x1 + 1, y1), (x1, y1 - 1), (x1, y1 + 1)]
                    if _is_valid(x2, y2)]

        # k足够将清理出一条最短路径
        if k >= (m + n - 2):
            return m + n - 2

        # dp[i][j][k] = 剩余k次消除术到达(i,j)的最小步数
        dp = [[[MAX_INT] * (k + 1) for _ in range(n)] for _ in range(m)]
        dp[0][0][k] = 0

        queue = collections.deque([(0, 0, k)])
        while queue:
            for _ in range(len(queue)):
                i1, j1, s1 = queue.popleft()
                v1 = dp[i1][j1][s1]
                for i2, j2 in neighbors(i1, j1):
                    if grid[i2][j2] == 0:
                        if v1 + 1 < dp[i2][j2][s1]:
                            # print(i2, j2, s1, ":", v1 + 1)
                            dp[i2][j2][s1] = v1 + 1
                            queue.append((i2, j2, s1))
                    elif s1 > 0:
                        if v1 + 1 < dp[i2][j2][s1 - 1]:
                            # print(i2, j2, s1 - 1, ":", v1 + 1)
                            dp[i2][j2][s1 - 1] = v1 + 1
                            queue.append((i2, j2, s1 - 1))

        ans = min(dp[-1][-1])
        return ans if ans < MAX_INT else -1


if __name__ == "__main__":
    # 6
    print(Solution().shortestPath(grid=
                                  [[0, 0, 0],
                                   [1, 1, 0],
                                   [0, 0, 0],
                                   [0, 1, 1],
                                   [0, 0, 0]],
                                  k=1))

    # -1
    print(Solution().shortestPath(grid=
                                  [[0, 1, 1],
                                   [1, 1, 1],
                                   [1, 0, 0]],
                                  k=1))
